package chapter2;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Hang
 * @date 2022/8/8
 * @project AutumnOffer
 * @description 面试题7
 **/
public class buildTree {
    private static Map<Integer,Integer> indexMap;
    public static void main(String[] args) {
        int[] preorder = new int[]{3,9,20,15,7};
        int[] inorder = new int[]{9,3,15,20,7};
        System.out.println(buildTree(preorder, inorder).val);
    }
    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length; // 获取数组长度
        indexMap = new HashMap<>(); // 使用map存放中序遍历
        for(int i=0;i<n;i++){
            indexMap.put(inorder[i],i); // 值在前，索引在后
        }
        return myBuildTree(preorder,inorder,0,n-1,0,n-1);
    }
    public static TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right){
        if(preorder_left>preorder_right){ // 前序遍历左子树大于右子树
            return null;
        }
        int preorder_root = preorder_left; // 获取树的根节点
        int inorder_root = indexMap.get(preorder[preorder_root]);// 获取根节点在中序遍历的下标
        TreeNode node = new TreeNode(preorder[preorder_root]); // 将该节点作为根节点重建二叉树
        int size_left = inorder_root - inorder_left; // 获取左子树的大小
        // 递归地连接左右子树到根节点
        node.left = myBuildTree(preorder,inorder,preorder_left+1,preorder_left+size_left,inorder_left,inorder_root-1);
        node.right = myBuildTree(preorder,inorder,preorder_left+size_left+1,preorder_right,inorder_root+1,inorder_right);
        return node;
    }
}
class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
